#include <iostream>
#include <cstdlib>
#include <list>
#include <string>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef char TElemType;
typedef struct HuffmanNode
{
	TElemType data;
	int weight;
	struct HuffmanNode *lchild, *rchild, *parent;
}HuffmanNode;

class HuffmanTree
{
public:
	HuffmanNode *root;
	HuffmanTree();
	HuffmanTree(TElemType data, int weight);
	HuffmanTree(HuffmanTree lchild, HuffmanTree rchild);
	Status InitHuffmanTree();
	Status DestroyHuffmanTree();
	Status CreateHuffmanTree(void (*func)(HuffmanNode *T));
	Status ClearHuffmanTree(HuffmanNode *T);
	bool HuffmanTreeEmpty();
	int HuffmanTreeDepth(HuffmanNode *T, bool isroot);
	HuffmanNode *Root();	
	TElemType Value(HuffmanNode *e);
	int Weight();
	Status Assign(HuffmanNode *e, TElemType value);
	HuffmanNode *Parent(HuffmanNode *e);
	HuffmanNode *LeftChild(HuffmanNode *e);
	HuffmanNode *RightChild(HuffmanNode *e);
	HuffmanNode *LeftSibling(HuffmanNode *e);
	HuffmanNode *RightSibling(HuffmanNode *e);
	Status InsertChild(HuffmanNode *p, int LR, HuffmanNode *c);
	Status DeleteChild(HuffmanNode *p, int LR);
	Status PreOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T, bool isroot);
	Status InOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T, bool isroot);
	Status PostOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T, bool isroot);
	Status LevelOrderTraverse(Status (*visit)(TElemType e));
	void Output(HuffmanNode *node, std::string);
	int WeighedLength(HuffmanNode *node, int length);
};
